class Solution {
public:
    int search(vector<int>& nums, int target) {
        /*
        直接顺序查找并统计target出现次数:时间复杂度O(n)
        */
        int times = 0;
        int sizeOfNums = nums.size();
        int i = 0;
        for(; i < sizeOfNums; ++i)
        {
            if(nums[i] == target)  break;
        }

        //统计target出现次数
        while(i < sizeOfNums && nums[i] == target)
        {
            ++times;
            ++i;
        }

        return times;
    }
};

/************************************************************/
class Solution {
public:
    int search(vector<int>& nums, int target) {
        /*
        因为数组是排序的，直接应用二分查找并统计target出现次数:target可能在数组中出现n次，
		所以这种做法实际时间复杂度为O(n)
        */
        int sizeOfNums = nums.size();
        if(sizeOfNums < 1)  return 0;

        int left = 0;
        int right = sizeOfNums - 1;
        int middle = 0;
        while(left <= right)
        {
            middle = (left + right) / 2;
            if(nums[middle] == target)  break;
            else if(nums[middle] > target)  right = middle - 1;
            else  left = middle + 1;
        }

        int times = 0;
        int i = middle;
        while(i >= left && nums[i] == target)
        {
            ++times;
            --i;
        }
        i = middle + 1;
        while(i <= right && nums[i] == target)
        {
            ++times;
            ++i;
        }

        return times;
    }
};

/*****************************************************************************************************/
class Solution {
public:
    int search(vector<int>& nums, int target) {
        /*
        (剑指)应思考如何充分优化二分查找，使得时间复杂度确定为O(logn)；
        我们的目的在于确定第一个target以及最后一个target的位置，可考虑使用二分查找确定这两个位置;
        使用递归实现查找两个位置的过程
        */
        int sizeOfNums = nums.size();
        if(sizeOfNums < 1)  return 0;

        int left = 0;
        int right = sizeOfNums - 1;
        int times = 0;
        if(left <= right)
        {
            int first = getFirstTarget(nums, target, left, right);
            int last = getLastTarget(nums, target, left, right);
            if(first > -1 && last > -1)  times = last - first + 1;
        }

        return times;
    }

    //寻找第一个target位置
    int getFirstTarget(vector<int>& nums, int& target, int left, int right){
        if(left > right)  return -1;

        int middle = (left + right) / 2;
        if(nums[middle] == target)
        {
            //判断是否是第一个target
            if((middle > 0 && nums[middle - 1] != target) || middle == 0)  return middle;
            else  right = middle - 1;
        }
        else
        {
            if(nums[middle] > target)  right = middle - 1;
            else  left = middle + 1;
        }

        return getFirstTarget(nums, target, left, right);
    }

    //寻找最后一个target位置
    int getLastTarget(vector<int>& nums, int& target, int left, int right){
        if(left > right)  return -1;

        int middle = (left + right) / 2;
        if(nums[middle] == target)
        {
            //判断是否是最后一个target
            if((middle < nums.size() - 1 && nums[middle + 1] != target) || middle == nums.size() - 1)  return middle;
            else  left = middle + 1;
        }
        else
        {
            if(nums[middle] > target)  right = middle - 1;
            else  left = middle + 1;
        }

        return getLastTarget(nums, target, left, right);
    }
};